/*
堆排序

堆是一棵完全二叉树，任何一个非叶子节点都不大于（或小于）其左右孩子节点的值

基本思想
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。
将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），
然后将剩余的 n-1 个序列重新构造成一个堆，得到 n 个元素中的次大值。
如此反复执行，便能得到一个有序序列了。


具体步骤
1. 将待排序序列构造成一个大顶堆。
2. 此时，整个序列的最大值就是堆顶的根节点。
3. 将其与末尾元素进行交换， 此时末尾就为最大值。
4. 然后将剩余 n-1 个元素重新构造成一个堆， 这样会得到 n 个元素的次小值。 
如此反复执行， 便能得到一个有序序列了。

最好时间复杂度：O(NlogN)
最坏时间复杂度：O(NlogN)
平均时间复杂度：O(NlogN)
空间复杂度：O(1)

稳定排序:否
原地排序:是
*/

#include "../../include/common.h"

void heapify(ElementType tree[], int n, int i){
    if (i >= n)
        return;
    
    //当前父节点的两个子节点
    int c1 = 2 * i + 1;
    int c2 = 2 * i + 2;
    //假设根节点为最大值
    int max = i;
    // 找出子树中三个节点中的最大的节点
    // if (c1 < n )
    // {
    //      max = (tree[c1] > tree[max]) ? c1:c2;
    // }
    if (c1 < n && tree[c1] > tree[max])
        max = c1;

    if (c2 < n && tree[c2] > tree[max])
        max = c2;
    //将最大节点和当前节点交换位置
    if (max != i){
        Swap(tree, max, i);
        //继续进行下一个节点的 构建堆
        heapify(tree, n, max);
    }
}


int build_heap (ElementType tree[],int n){
    int last_node = n-1;
    //最后一个父节点
    int parent = (last_node-1)/2;
    int i;
    //从最后一个父节点开始，由下到上遍历每一个父节点依次调整构建堆
    for(i = parent; i>=0; i--)
        heapify(tree,n,i);
}


int HeapSort (ElementType tree[],int n){
    //构建堆 第一个节点为堆中最大的数
    build_heap(tree,n);
    int i;
    //每次都换出来一个最大值
    for(i = n-1; i>=0; i--) {
        //交换最后一个节点和第一个节点
        Swap(tree, i, 0);
        //每次都截断最后一个元素，我们可以默认最后一个元素已经被截断了，i即为剩下的元素，每次传入i的值即可继续构建0--i范围内的元素
        heapify(tree, i, 0);
    }
}



/*-----------------------------------------------------------------*/
void AdjustDown(ElementType arr[], int k, int len){
    ElementType temp = arr[k];
    int i;
    for (i=2*k; i<len; i*=2){
        if (i < len && arr[i] < arr[i+1])
            i++;
        if (temp >= arr[i])
            break;
        else {
            arr[k] = arr[i];
            k = i;
        }
        arr[k] = temp;
    }
}

void BuildMaxHeap(ElementType arr[], int len){
    int i;
    for (i = len/2; i>0; i--)
        AdjustDown(arr, i, len);
}

void HeapSort(ElementType arr[], int len){
    BuildMaxHeap(arr, len);
    int i;
    for (i=len-1; i>0; i--){
        Swap(arr, i, 0);
        AdjustDown(arr, 0, i);
    }
}